package 排序.快速排序;

import java.util.Arrays;

public class Solution
{
    //采用随机数的基准选取方法
    /*
    把即基准小的放在一边，比基准大的放在另一边
     */
    public int Partition(int[] array,int start,int end) throws Exception
    {
        //判断输入
        if (array==null||start<0||end>=array.length)
            throw new Exception("错误的参数");
        int index=(int)(Math.random()*(end-start));
//        index=start;
        Swap(array,index,end);
        int small=start-1;
        for (index = start; index < end; index++)
        {
            //比index小的放到左边，大的放到右边，此处的end实际是交换之前的index随机数
            if (array[index]<array[end])
            {
                ++small;
                if (array[small]!=array[index])
                    Swap(array,index,small);
            }
        }
        //small最后停的位置就是最近 一个小于随机数的位置，把small向前进1，得到最近的一个比随机数大的位置，把一开始交换的后面的随机数换回来
        ++small;
        Swap(array,small,end);
        return small;
    }
    public void Swap(int[] array,int a ,int b)
    {
        int temp=array[a];
        array[a]=array[b];
        array[b]=temp;
    }
    public void QuickSort(int[] array,int start,int end) throws Exception
    {
        if (start==end)
            return;
        int index=Partition(array,start,end);
        if (index>start)
            QuickSort(array,start,index-1);
        if (index<end)
            QuickSort(array,index+1,end);
    }

    public static void main(String[] args) throws Exception
    {
        Solution solution = new Solution();
        int[] test=new int[]{2,4,5,1,8,3};
        solution.QuickSort(test,0,test.length-1);

        System.out.println(Arrays.toString(test));


    }
}
